思路:数据这么小,根据题意模拟即可。
具体做法:
- 判断第一个数的值,若等于 则进入第四步。
- 根据题意对每个数遍历进行修改。
- 回到第一步,直到符合题意为止。
- 输出统计得到的结果即可。
但是这个程序的正确性依赖于整个过程中的单调不降性质,需要证明:
对于相邻两个数 和 :
- 如果 ,不进行修改, 与 依然相等。
- 如果 ,将 加一,此时 。
由于初始序列单调不降,因此任意时刻,数列满足单调不降。
程序的正确性得证。
一个小 trick:C++ 中单独的逗号语句的值为最后一个逗号后的表达式的值,与前面无关,因此可以通过这个简写一些代码。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, k, a[N], ans;
int main() {
scanf("%d%d", &n, &k);
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
do {
if(a[1] == k) return printf("%d\n", ans), 0;
for(int i=1;i<=n;i++) {
if(a[i] < k && a[i] != a[i+1]) ++a[i];
}
}while(++ans, true);
return 0;
}